1. Field of the Invention
The invention generally relates to a technique that employs dithering for producing a halftoned bit pattern for reproduction on a binary printer having a limited, though preferably a relatively high, resolution where the halftoned bit pattern has a relatively fine screen ruling and, for a given sized dither matrix, can depict an increased number of gray levels and specifically to such a technique that employs both dithering and error propagation.
2. Description of the Prior Art
Although electronic communication is becoming rather ubiquitous, currently the printed page is still the predominant form of communication. A printed page contains text, graphics and/or images.
In the graphic arts industry, a page that will be mass reproduced is commonly referred to as an artwork. Traditionally, artworks were produced using manual document creation and page composition processes. Unfortunately, such manual processes proved to be tedious and costly. As such, electronic systems that create images, graphics and text and provide electronic page composition capabilities are seeing increasing use. With these electronic systems, an artwork, owing to its inclusion of graphics and/or images, is often stored in bit-mapped form for reproduction on an output device, such as a printer. For black and white artworks, each location in the bit-map contains a binary value that specifies whether that location in the artwork is either white or black. For gray level or color artworks, each location in a pixel-map contains a multi-bit value that respectively corresponds to the particular color or monochromatic shade that exists at that location in the artwork. Now, even though an artwork can be processed and stored electronically, a paper reproduction of that artwork onto a printed page will ultimately need to be made, particularly if that page will form part of a publication, such as a magazine.
Currently, printing presses of one form or another are generally used to provide accurate mass reproductions of a color artwork. To avoid the need to use a differently colored ink in the press to print each different color in the artwork, current printing techniques rely on the fact that many colors can be obtained as a linear combination of four primary subtractive colors: cyan, yellow, magenta and black. As such, to print a multi-colored artwork, four printed monochromatic images, each made from a corresponding primary colored ink, are successively made in separate printing passes on a common sheet of printing stock and overlaid on that sheet with proper registration to yield a single multi-colored page that, when viewed by an observer, accurately replicates the tonal colorations of a given artwork.
In particular, a colored artwork that is to be printed is first separated, typically by optical filtering and photographic processes, into four primary color continuous tone ("contone") separations. Each separation is essentially a monochromatic two-dimensional depiction on a transparent medium of density values for the color information for only one of the primary colors in the artwork. As such, a different separation exists for cyan, yellow, magenta or black. However, only one separation (typically black) would be used for single color gray-scale artworks. Unfortunately, printing presses are not able to apply a differential amount of a colored ink to any one location in a page. As such, a printing press can not directly print a contone separation. To surmount this obstacle, the art teaches the use of halftone separations. A halftone separation is formed through screening a contone separation. With no tonal variations, each halftone separation contains a regularly spaced two-dimensional pattern of relatively small monochromatic dots with a resolution in most graphic arts applications of at least 85 dots/inch (approximately 34 dots/centimeter (cm)). Such a regular dot pattern has a relatively high spatial frequency. As a result of screening a contone separation that has tonal variations, the tonal variation from one location to the next in the separation changes the diameter of the dots located in corresponding locations in a halftone separation (i.e. the diameter of individual dots increases while the center-to-center spacing between adjacent dots remains constant as the contone values increase) thereby spatially modulating the underlying regular halftone dot pattern for that color. Hence, when the halftone separation is viewed by a human eye, the modulated pattern is integrated by the eye to yield the corresponding tonal variations. Once the four halftone separations are made, these separations are transferred to separate printing plates which, in turn, are subsequently used to print four halftone separation patterns on common sheets of printing stock with proper registration. When the resulting printed sheet is then viewed by an observer, an accurate depiction of the desired colored artwork results from the spatial interaction of the four overlaid primary colored halftone separation patterns.
In well known lithographic printing techniques, each primary color contone separation is photographically generated from a contone image and then photographically screened, with different appropriate rotations that minimize objectionable Moire patterns, to yield a halftone separation. All the halftone separations of this contone image are then photographically combined to produce a "proof" image. Thereafter, if the proof image is acceptable, each halftone separation is then photographically transferred to a printing plate. This process which is manual is often tedious, time consuming and expensive. Hence, in an effort to reduce the time, expense and tedium associated with such manual photographic based processes, the art has turned to electronic techniques that are capable of directly printing a halftone separation form a contone separation. These techniques employ an electronic printer that has a relatively high resolution for directly printing a halftone separation on a suitable medium.
One such high resolution printer which is advantageously capable of and particularly suited for directly printing halftone separations is the IBM Model 4250 electro-erosion printer (IBM is a registered trademark of the International Business Machines Corporation in Armonk, N.Y.). This printer utilizes a special printing media formed of a thin aluminum layer overlaying either a dark contrast layer or a transparent undercoat. During printing, the printer produces each darkened pel in a printed page on this printing media by selectively vaporizing (electro-eroding) the aluminum film which is situated at that pel location on the print media. If printing media with a dark contrast layer is used, then this media, when eroded, could serve as a camera ready master for a halftone separation. Alternatively, if printing media with a transparent undercoat is used, then this media, when eroded, could serve as either a camera ready negative or short run printing plate. Through this printing process, this printer is able to provide an all points addressable resolution of 600 dots (pels) per inch which provides a printed halftone separation that is able to clearly depict rather fine detail.
To achieve very smooth edges on printed characters, rules and graphics, the IBM 4250 electro-erosion printer prints adjacent writing spots on a partially over-lapping basis. Inasmuch as the resolution of this printer, specifically 600 dots/inch (approximately 236 dots/cm), exceeds that at which a contone separation is typically scanned, the numeric density of the contone values must be upwardly scaled to match the resolution of this printer. Accordingly, a group of contone values in the scaled contone separation has a non-overlapping halftone block corresponding thereto and correspondingly situated in the printed bit-map therefor.
Printing halftone dots with varying diameters using such electronic printers has proven to be difficult. As such, dither techniques are often used instead. Specifically, with a dither technique, different gray values are reproduced by printing a specific pre-defined halftone pattern in each halftone block or by thresholding each scaled contone value with an appropriate threshold in a dither matrix. Depending upon the contone value associated therewith and the particular type of dither pattern being used, a halftone block may contain either a clustered or dispersed pattern of printed pels within that block. Inasmuch as a dither pattern is spatially integrated by the human eye, the illusion of a gray scale variation is provided by printing an increased or decreased number of darkened pels in the pattern for each halftone block. The resultant output pattern has a definite structure, i.e. a grid at a pre-defined angle, that advantageously appears very similar to a corresponding pattern of halftone dots produced by well known photographic screening processes.
The art teaches that the size of a halftone block is dictated by two opposing factors: as the size of each halftone block increases, the number of gray levels that can be depicted by that block increases inasmuch as there are additional pixels that can be successively darkened to provide additional dither patterns, however the resolution of the resulting halftoned image may simultaneously decrease, i.e. as the block increases in size the halftoned image becomes increasingly grainy. Moreover, as the size of each halftone block increases, low frequency patterns tend to appear in areas of uniform gray level that occur in the halftoned image.
Currently, high quality image scanners produce a resolution of approximately 200 pixels/inch (approximately 79 dots/cm) or higher. With a printable resolution of 600 dots/inch provided by the IBM 4250 printer and with these constraints on halftone block size in mind, the art teaches that use of a rectangular halftone block of 3 by 6 pels for a total of 18 pels provides a good quality halftoned separation. Each block is associated with two adjacent input pixels and generally represents the gray value that is closest to the average value of the two pixels. By using 18 pels, each halftone block can be used to depict any one of 18 different dither patterns. Each dither pattern varies from a previously occurring pattern by the simple addition of one darkened pel to the previous pattern. Use of such a halftone block provides a screen ruling of 141 lines/inch (approximately 56 lines/cm) which approximately matches the 150 lines/inch (approximately 59 lines/cm) resolution used in high quality printing applications. In addition, each contone separation is scanned at a resolution of 200 pixels/inch.
I have found that in most instances 18 different gray levels are simply not enough to impart sufficient color variation to a color image formed of halftoned separations that have been directly printed through use of such a high resolution printer. In general, an insufficient number of gray levels tends to exist whenever a relatively small sized halftone block is used to provide a fine grained halftoned image.
Unless one is willing to accept a loss of resolution in the halftoned image----which is rarely the case, then the size of each halftone block can not be increased. As such, this fixes the size of each halftone block in the screened image. Now, it is well known in the art that the size of the dither matrix, i.e. the number of pels in a halftone block, limits the number of available gray levels that can be depicted by dither patterns residing therein. For example, with a dither matrix having 18 pels, the art teaches that this matrix can depict 18 different gray levels. See, e.g., R. Ulichney, Digital Halftoning, (London: The MIT Press, .RTM. 1987) and particularly pages 84-98 thereof. In this regard, changing the individual dither patterns, such as from clustered to dispersed, without changing the size of the dither matrix itself has no affect on the number of available gray levels. As such, the art teaches that once the size of the dither matrix is fixed, then the number of available gray levels is also fixed with no intermediate gray levels capable of being produced.
Therefore, a need exists in the art for a technique that employs dithering for producing a halftoned bit pattern for reproduction on a relatively high resolution binary printer where the halftoned bit pattern has both a relatively fine screen ruling and can depict an increased number of gray levels for a given sized dither matrix over that heretofore taught in the art. Advantageously, this technique should produce an increased number of gray levels with nearly any, if not all, different halftone dither patterns and impart little, if any, low frequency patterns to the halftoned image.